/*
题目: 单词接龙
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

    每一对相邻的单词只差一个字母。
     对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
    sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。
如果不存在这样的转换序列，返回 0 。
https://leetcode.cn/problems/word-ladder/
 */
public class LadderLength {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 提高查询效率
        Set<String> dict = new HashSet<> ();
        for (String s : wordList)
            dict.add(s);

        // 记录有没有访问过
        Set<String> visited = new HashSet<> ();
        if (!dict.contains(endWord))    return 0;
        // 每个 String 变换一个字符, 如果在词典里, 就入队, 如果是 endWord , 就返回
        Queue<String> queue = new LinkedList<> ();
        queue.offer(beginWord);
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();

            while (size-- > 0) {
                StringBuilder cur = turnStringBuilder(queue.poll());

                for (int i = 0; i < cur.length(); i++) {
                    char tmp = cur.charAt(i);
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        if (ch == tmp)  continue ;
                        cur.setCharAt(i, ch);
                        String str = cur.toString();

                        // 如果访问过了
                        if (visited.contains(str)) {
                            continue ;
                        }
                        if (str.equals(endWord)) {
                            return step + 1; // 单词数目
                        }
                        // 在字典里, 有可能得到答案, 加入队列, 并标记为访问过
                        if (dict.contains(str)) {
                            queue.offer(str);
                            visited.add(str);
                        }
                    }
                    cur.setCharAt(i, tmp);  // 改回原字符
                }
            }
            step ++;
        }

        return 0;
    }

    private StringBuilder turnStringBuilder(String s) {
        StringBuilder ret = new StringBuilder();
        ret.append(s);
        return ret;
    }
}
